package com.dmall.chapter03.section04;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 使用map数据结构
 * 时间复杂度：只有一层for循环，所以时间复杂度是：O(n)
 * 空间复杂度：O(n)，由于使用了一个map存数据，所以空间复杂度是：O(n)
 * @author xiao1.wang
 * @date 2020-12-01 22:38:34
 */
public class Leetcode1V3 {

    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(nums.length * 100 / 75 + 1);
        for (int i = 0; i < nums.length; i++) {
            int subRes = target - nums[i];
            if (map.containsKey(subRes)) {
                return new int[] {map.get(subRes), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        Leetcode1V3 leetcode1 = new Leetcode1V3();
        int[] res = leetcode1.twoSum(nums, 26);
        System.out.println(Arrays.toString(res));
    }
}
